package unionfind;

import java.util.HashSet;
import java.util.Set;

/**
 * @author pengfei.hpf
 * @date 2020/3/5
 * @verdion 1.0.0
 *
 * 在二维平面上，我们将石头放置在一些整数坐标点上。每个坐标点上最多只能有一块石头。
 *
 * 现在，move 操作将会移除与网格上的某一块石头共享一列或一行的一块石头。
 *
 * 我们最多能执行多少次 move 操作？
 *
 *  
 *
 * 示例 1：
 *
 * 输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
 * 输出：5
 * 示例 2：
 *
 * 输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
 * 输出：3
 * 示例 3：
 *
 * 输入：stones = [[0,0]]
 * 输出：0
 *  
 *
 * 提示：
 *
 * 1 <= stones.length <= 1000
 * 0 <= stones[i][j] < 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/most-stones-removed-with-same-row-or-column
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class RemoveStones {
    int[] parent = new int[20000];
    //TODO: 并查集 将二维的数组降到一维 技巧
    public int removeStones(int[][] stones){
        if(stones == null || stones.length <= 1){
            return 0;
        }
        int n = stones.length;
        for(int i = 0; i < n; i ++){
            parent[stones[i][0]] = stones[i][0];
            parent[stones[i][1] + 10000] = stones[i][1] +10000;
        }
        for(int i = 0; i < n; i ++){
            union(stones[i][0], stones[i][1]+10000);
        }
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < n; i ++){
            set.add(find(stones[i][0]));
        }
        return n - set.size();
    }

    private int find(int x){
        int p = x;
        while(parent[p] != p){
            p = parent[p];
        }
        parent[x] = p;
        return p;
    }

    private void union(int x, int y){
        int a = find(x);
        int b = find(y);

        parent[b] = a;
    }
}
